import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
/*
题目描述
请实现一个函数按照之字形打印二叉树，
即第一行按照从左到右的顺序打印，
第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

思路：
（1）每一层最后设置null
（2）或者两个栈实现

*/

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}

public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        TreeNode level = new TreeNode(-1);
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        ArrayList<Integer> temp;
        TreeNode node;
        Queue<TreeNode> queue = new ArrayDeque<>();
        if(pRoot==null)
            return result;
        else{
            queue.add(pRoot);
            queue.add(level);
            temp = new ArrayList<>();

            while(!queue.isEmpty()){
                node = queue.poll();
                if(node==level){
                    result.add(temp);
                    temp = new ArrayList<>();
                    if(!queue.isEmpty()){
                        queue.add(level);
                    }
                }else{
                    temp.add(node.val);
//                    System.out.println(node.val);
                    if (node.left!=null)
                        queue.add(node.left);
                    if(node.right!=null)
                        queue.add(node.right);
                }
            }
        }
        int i = 0, tempi;
        for (ArrayList list : result) {
            if(i%2!=0){
                for(int k = 0; k<list.size()/2; k++){
                    list.get(k);
                    tempi = (int)list.get(k);
                    list.set(k,list.get(list.size()-k-1));
                    list.set(list.size()-k-1,tempi);
                }
            }
            i =i+1;

        }
        return result;
    }
    public static void main(String args[]){
        Solution s = new Solution();
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        s.Print(node1);
    }

}